/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/toeplitz-matrix
   @Language: C++
   @Datetime: 19-05-06 15:42
   */

class Solution {
public:
	/**
	 * @param matrix: the given matrix
	 * @return: True if and only if the matrix is Toeplitz
	 */
	bool isToeplitzMatrix(vector<vector<int> > &matrix) {
		// Write your code here
		int n=matrix.size(), m=matrix.size()>0?matrix[0].size():0;
		for(int col=0; col<m; ++col){
			const int key=matrix[0][col];
			for(int i=0; i<n && col+i<m; ++i)
				if (matrix[i][col+i]!=key) return false;
		}
		for(int row=0; row<n; ++row){
			const int key=matrix[row][0];
			for(int i=0; row+i<n && i<m; ++i)
				if (matrix[row+i][i]!=key) return false;
		}
		return true;
	}
};
